/*
 * @lc app=leetcode.cn id=994 lang=typescript
 *
 * [994] 腐烂的橘子
 */

// @lc code=start
interface Cell {
  i: number;
  j: number;
  step: number;
}

function orangesRotting(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const queue: Cell[] = [];
  let fresh = 0;
  // 遍历所有的橘子，将腐烂的橘子入队，统计新鲜橘子数量
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) {
        queue.push({ i, j, step: 0 });
      } else if (grid[i][j] === 1) {
        fresh++;
      }
    }
  }

  const dirs = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  let ans = 0;
  while (queue.length) {
    const curr = queue.shift()!;
    ans = curr.step;
    // 向四个方向扩散，找到新鲜橘子
    for (const dir of dirs) {
      const i = curr.i + dir[0];
      const j = curr.j + dir[1];
      if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== 1) {
        continue;
      }
      grid[i][j] = 2;
      fresh--;
      queue.push({ i, j, step: curr.step + 1 });
    }
  }

  // 搜索完毕，如果还有新鲜橘子，说明不可达
  return fresh ? -1 : ans;
}
// @lc code=end
